class Solution:
    def racecar(self, target: int, step: int = 0, speed: bool = True) -> int:
        # speed变量表示是否将速度重置为正向速度1
        # 重置速度且不变向需要2步，我们将这种情况称为正向重置
        # 重置速度且变向只需要1步，我们将这种情况称为反向重置

        # 推论1：
        # 每次我们可以不用重置速度地移动2^k-1的距离，如果目标点我们可以不用重置速度地移动到；那么直接重置速度并开始运行一定是最优解

        # 在不能直接移动的情况下；我们都有两种选择：
        # 方案1：不重置速度地目标点之后的第一个点，然后回头转向
        # 方案2：不重置速度地到达目标点之前的最后一个点，然后重置速度走向终点

        # 对于方案1：
        # 如果当前已经重置速度，我们在回头前反向重置；
        # 如果当前没有重置速度，我们可以直接反向重置先走第2段路程，然后再反向重置走第1段路程。
        # 综上所述，如果没有重置速度，我们需要2次反向重置；如果已经重置速度，我们需要1次反向重置

        # 对于方案2：
        # 如果当前已经重置速度，我们需要在完成第1段路程后正向重置1次；
        # 如果当前没有重置速度，我们需要完成在两段路程前正向重置2次。

        # 在实现中：
        # 对于方案1来说，如果当前没有重置速度，则需要额外增加一次反向重置（1步）；
        # 对于方案1来说，如果当前没有重置速度，则需要额外增加一次正向重置（2步）；

        # 因此，有可能下一段层级的路程来说，可能宁可接受未重置速度的情况，自己执行两次反向重置，也不需要在上一个层级就先正向重置速度。
        # 所以，在实现中，正向重置我们不执行，而是将未重置的状态直接递归给下一个层级让下一个层级自己做出选择。
        # 例如target=2就符合上述情况，2次反向重置虽然走了更远的路程，但是仍然优于2次正向重置。

        print("当前步数:", step, "目标:", target, "是否重置速度:", speed)

        # 定义递归终点的特殊情况
        if target == 0:
            return step

        # 计算当前的方案1和方案2的位置
        k = target.bit_length()

        # 处理推论1中的情况
        if target == (2 ** k) - 1:
            return step + k + (2 if not speed else 0)

        # 计算方案1的第1段路程的目标位置、到达目标位置所需的步数
        choose1, step1 = (2 ** k - 1), k
        # 计算方案1的第2端路程的距离
        distance1 = choose1 - target
        # 计算方案1需要的重置步数（两段子路程均为已重置的情况）
        reset1 = 1 + (1 if not speed else 0)

        # 计算方案2的第1端路程的目标位置、到达目标位置所需的步数
        choose2, step2 = (2 ** (k - 1) - 1), k - 1
        # 计算方案2的第2端路程的距离
        distance2 = target - choose2
        # 计算方案2需要的重置步数（第2段路程为未重置的情况）
        reset2 = (2 if not speed else 0)

        return min(
            self.racecar(distance1, step + step1 + reset1, True),
            self.racecar(distance2, step + step2 + reset2, False),
        )


if __name__ == "__main__":
    print(Solution().racecar(3))  # 2
    print(Solution().racecar(5))  # 7
    print(Solution().racecar(6))  # 5
    print(Solution().racecar(20))  # 12
